package _08;
/*问题描述
　　如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。
　　小明想知道，长度为 m，每个数都是 1 到 n 之间的正整数的摆动序列一共有多少个。
输入格式
　　输入一行包含两个整数 m，n。
输出格式
　　输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。
样例输入
3 4
样例输出
14
样例说明
　　以下是符合要求的摆动序列：
　　2 1 2
　　2 1 3
　　2 1 4
　　3 1 2
　　3 1 3
　　3 1 4
　　3 2 3
　　3 2 4
　　4 1 2
　　4 1 3
　　4 1 4
　　4 2 3
　　4 2 4
　　4 3 4
评测用例规模与约定
　　对于 20% 的评测用例，1 <= n, m <= 5；
　　对于 50% 的评测用例，1 <= n, m <= 10；
　　对于 80% 的评测用例，1 <= n, m <= 100；
　　对于所有评测用例，1 <= n, m <= 1000。*/

import java.util.Scanner;

public class _08 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        sc.close();
        //dp[i][j] i表示第多少位，j表示一个分界线
        //	奇数行就是大于j的方案数，偶数行就是小于j的方案数
        //	奇数要比前面的大，所以要大于的，偶数要比前面的小，所以要小于的

        int[][] dp = new int[m + 2][n + 2];
        //初始化边界
        for (int i = 1; i <= n; i++) {
            dp[1][i] = n - i + 1;
        }

        for (int i = 2; i <= m; i++)
            if ((i & 1) == 1) {
                //奇数的话是要比前面大的,所以用倒序
                for (int j = n; j >= 1; j--) {
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i][j + 1]) % 10000;
                }
            } else {
                for (int j = 1; j <= n; j++) {
                    dp[i][j] = (dp[i - 1][j + 1] + dp[i][j - 1]) % 10000;
                }
            }
        //m&1，就是把m换成二进制看看最后一位是不是1，如果是1证明就是奇数，如果是0证明是偶数
        int result = (m & 1) == 1 ? dp[m][1] : dp[m][n];
        System.out.println(result);

    }
}


